1. Field of the Invention
The present invention relates to a computer system, and deals more particularly with a method, system, and computer readable code for improving user exploration (i.e. navigation and browsing) through hierarchies of information. Entity relevance is calculated for the entities in the hierarchies, and this information is used to guide the user in his exploration.
2. Description of the Related Art
The continuing proliferation of electronic media has resulted in an explosion in the availability of electronic catalogs, such as those used for managing parts within corporations and for selling products to consumers. Accompanying this growth is the continued investigation and implementation of different browsing strategies that offer intuitive techniques to aid users when searching and navigating large spaces of information. Providing easy-to-use facilities for the end-user is a key factor in the successful deployment of an electronic catalog, especially in today""s highly competitive environment.
Categories in an electronic catalog are often arranged hierarchically, forming a category hierarchy, where the nodes of the hierarchy represent categories and sub-categories. A category hierarchy typically represents an embodiment of a particular type of association among category nodes as well as between category nodes. This association may represent: classification, decomposition, generalization, etc. For example, in a classification-based category hierarchy, a category serves to classify its sub-categories. On the other hand, in a decomposition-based category hierarchy, a category serves as a composite of parts, represented by its sub-categories. (Hereinafter, the term xe2x80x9ccategoryxe2x80x9d will be used to refer to both categories and sub-categories, unless otherwise stated.) An entity (e.g., product) associated with a category represents an instance of the category, and that instance is a representative of that category.
Within an electronic catalog, the categories themselves and their arrangement to one another are engineered so as to provide intuitive navigational benefits to the catalog user in search of products. The majority of electronic catalogs in popular use today (such as those which may be created using the Net.Commerce product available from the IBM Corporation) have some category structure (i.e., node hierarchy) under which parts or products are categorized. FIG. 1A depicts a simple example of a product category hierarchy 100. The highest-level node 105, or root, of the hierarchy indicates that this is a hierarchy of computers. The next level in the hierarchy has two nodes, xe2x80x9cWorkstationxe2x80x9d 110 and xe2x80x9cServerxe2x80x9d 115, where each of these nodes serves to more specifically classify different types of computers. The lowest level of the example hierarchy depicts two nodes organized under each of the Workstation and Server nodes, indicating that both of these categories have two sub-categories (120 and 125, and 130 and 135, respectively). As will be obvious, the hierarchies of actual electronic catalogs are typically much more complex, having many more levels and many more nodes at each level, than the example shown in FIG. 1A.
Use of a corporation""s electronic catalogs may be limited to internal use within the corporation, or the catalogs may be designed for external use by customers. And, some electronic catalogs are used both internally and externally. An example of the internal use scenario is a catalog for parts inventory management, implemented using a bill-of-materials approach where a complex part corresponds to a high-level category, and the parts from which it is constructed then correspond to lower-level categories. An example of the external use scenario is the electronic catalogs which are becoming increasingly popular for electronic shopping using the Internet and World Wide Web (hereinafter, xe2x80x9cWebxe2x80x9d). These electronic catalogs appear in different forms and many different applications. Many on-line retailers offer an electronic version of their traditional printed catalog, such as those used for selling clothing, office supplies, etc. These electronic catalogs are typically organized using a category hierarchy similar to the index of the printed catalog, with which the retailer""s customers are already familiar. Hierarchical categories are also commonly used for the increasingly-popular on-line auction services, where a vast array of products being offered at auction are organized into a hierarchy of categories to conveniently direct a shopper""s attention to the items corresponding to his personal interest.
Electronic catalogs typically provide some form of search or navigation capability that users can employ in the location of parts or products. Search capabilities include entry of a specific item number, and keyword searches. Using this approach, a user may view a part or product directly, without regard to how it has been categorized. For example, if a user enters an item number corresponding to a particular model of desktop computer, he may be unaware that it has been categorized as a desktop computer, which is a type of workstation, which is a type of computer (using the example of FIG. 1A). However, the absence of the categorization information is a drawback of this approach. Suppose, for example, that the user has incorrectly recorded the item number: an item number search will not enable him to locate the product he is interested in. Keyword searches can also be problematic, where complex Boolean relationships between keywords may be needed in order to successfully locate a specific product. Entering too few keywords may result in an overly broad and therefore unusable result, while entering too many may cause relevant products to be omitted. Without information about the category hierarchy, the user may not be able to easily refine his keyword search to use an appropriate set of keywords.
Categories may also be navigated in a hierarchical manner as the user looks for a part or product, or browsed hierarchically. Electronic catalogs employing catalog hierarchies are nearly always accompanied by some form of hierarchical navigation mechanism. Hierarchical navigation allows users to incrementally ascend and descend from node to node along the paths defining the hierarchy. Hierarchical navigation offers an alternative to search in the location of parts or products in an electronic catalog, essentially providing a roadmap through a catalog""s information space where the user can view relationships among categories as he moves from node to node. If there are multiple hierarchies in the catalog, a user is given the opportunity to move to another hierarchy by selecting that hierarchy""s root node and subsequently navigating from that point.
FIG. 1B depicts the example category hierarchy of FIG. 1A, which has now been augmented with instances of several of the categories. These instances are specific products (types of computers, in this example), and are collectively referred to as the xe2x80x9cproduct basexe2x80x9d, denoted in FIG. 1B by element 150. Instances in the general case (i.e. whether they are parts, products, etc.) within a hierarchy will be referred to hereinafter as xe2x80x9centitiesxe2x80x9d, and the collection of entities will be referred to as the xe2x80x9centity basexe2x80x9d. The user may hierarchically navigate this product categorization, for example, by beginning at the root node 105, where he learns from the hierarchical structure 100 that the computers in this catalog are further organized into workstations and servers. Suppose the user is interested in a laptop computer. He will therefore select to navigate to the Workstation node 110 instead of to the Server node 115. By his intuitive knowledge of computer descriptions, the user then realizes that the xe2x80x9cPortablexe2x80x9d category 125 is the next logical node for descending the hierarchy to find a laptop computer. Having reached a collection of entities 151, 152, 153, the user may then choose to view detailed information about the particular computer instances. The user may also choose to ascend the hierarchy, perhaps to view desktop computers as an alternative to portable computers, in which case he will navigate to (i.e. ascend to) the Workstation node 110 and then descend to the Desktop node 120.
Hierarchical browsing, in addition to allowing incremental descents and ascents of hierarchical navigation, allows users to make non-incremental descents and ascents in a hierarchy. It also enables users to make lateral movements across nodes within a hierarchy. In addition, when browsing multiple hierarchies, users are allowed to move to another hierarchy without having to continue their search from the new hierarchy""s root node. Referring to the example of FIG. 1B, hierarchical browsing would enable the user to traverse from the root node 105 directly to a lower-level node such as Desktop 120, and to move laterally from that node to another node such as Server 115 or Office Server 135.
A number of problems and inadequacies exist with current hierarchical navigation and hierarchical browsing capabilities. With reference to hierarchical navigation, these include: the limitation of using incremental descent and ascent for traversal; inability to make lateral movements within a hierarchy, or across multiple hierarchies; and the limitation of considering a single hierarchy at a time. With reference to hierarchical browsing, the inadequacies include that hierarchical browsing does not maintain a solution statexe2x80x94that is, which nodes have been selected/visited by the user. A solution state enables use of visited nodes as constraints in narrowing the user""s search for an entity. In effect, each subsequent visited node xe2x80x9cprunesxe2x80x9d the information space being traversed, such that these constraints serve as a boundary for the set of entities that may satisfy the user""s interest. Further, because hierarchical browsing does not maintain a solution state, a search strategy limited to this technique cannot reason about consistency between the constraints of the current solution state and the lateral nodes in a hierarchy (or across hierarchies). And, because hierarchical browsing cannot reason about consistency between the constraints of the current solution state and the lateral nodes in a hierarchy or across hierarchies, it is incapable of offering any guidance to a user as to which paths in the hierarchy lead to entities that remain consistent with his on-going search for a part or product.
Accordingly, a need exists for a technique by which these inadequacies in hierarchical navigation and hierarchical browsing can be overcome, in order to provide more intelligent and intuitive exploration through hierarchical information.
An object of the present invention is to provide a technique to improve exploration of category hierarchies.
Another object of the present invention is to provide a technique for improving user satisfaction with electronic catalogs.
It is a further object of the present invention to provide these techniques without requiring alteration of existing category hierarchies and/or electronic catalogs.
It is another object of the present invention to provide guidance for a user traversing a category hierarchy as to where entities that are relevant to an on-going search may be located.
It is yet another object of the present invention to provide guidance to a user as to which next node choices for paths through a category hierarchy remain consistent with his on-going search, and which are inconsistent.
Other objects and advantages of the present invention will be set forth in part in the description and in the drawings which follow and, in part, will be obvious from the description or may be learned by practice of the invention.
To achieve the foregoing objects, and in accordance with the purpose of the invention as broadly described herein, the present invention provides a system, method, and computer program product for use in a computing environment, for intelligent and improved exploration through one or more hierarchies of categorized information. In a first aspect, this technique comprises: providing one or more category hierarchies, where each of the hierarchies comprises a root node, one or more intermediate nodes, and one or more leaf nodes. Each of the root nodes and the intermediate nodes corresponds to a category in the hierarchy, and each of the leaf nodes corresponds to an entity categorized by said hierarchy. This first aspect further comprises: computing a structural relevance for each of the root nodes and the intermediate nodes; enabling a user to select a particular one of the root nodes or the intermediate nodes; computing a state relevance reflecting this selection; and computing a node feasibility reflecting this state relevance.
Computing the structural relevance preferably further comprises: determining a static set of strongly relevant, weakly relevant, irrelevant, and relevant ones of the entities for each of the root nodes and the intermediate nodes. Computing the state relevance preferably further comprises: determining a dynamic set of strongly relevant, weakly relevant, irrelevant, and relevant ones of the entities based upon a previous state of the dynamic set and the static set for the selected node.
Computing the node feasibility preferably further comprises: determining a feasible or non-feasible status of each of the root nodes and the intermediate nodes which have not yet been selected. This may further comprise: determining the status to be feasible when the static set of relevant ones for the selected node has at least one entity in common with the dynamic set of relevant ones, and determining the status to be infeasible otherwise.
The present invention will now be described with reference to the following drawings, in which like reference numbers denote the same element throughout.